// 给定一个升序数组nums和一个目标值target，找出给定目标值在数组中的开始位置和结束位置，要求使用时间复杂度为O(logn)
// 思路：需要用二分查找算法，分两次查找，第一次尽量向左搜索，第二次尽量向右搜索

function searchRange(nums, target) {
    let ans = [-1, -1]
    let left = 0
    let right = nums.length - 1
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        if (nums[mid] < target) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    if (nums[left] !== target) {
        return ans
    }
    ans[0] = left
    left = 0
    right = nums.length - 1
    while (left < right) {
        // 这里要注意往上取整
        let mid = Math.ceil((right - left) / 2) + left
        if (nums[mid] > target) {
            right = mid - 1
        } else {
            left = mid
        }
    }
    if (nums[right] === target) {
        ans[1] = right
    }
    return ans
}

// 时间复杂度为Ologn

let arr = [1, 2, 2, 3, 3, 3, 3, 3, 7]
console.log(searchRange(arr, 3));